import javax.swing.tree.TreeNode;
import java.util.List;

/**
 * Created by sunchenglin on 2017/7/2. 5
 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
 思路：
 （1）节点为空，返回空
 （2）该节点的右子树为空，
    该节点父亲为空：返回null
    该节点父亲非空：
        该节点是是父亲的左子树 ,返回该节点父亲节点。
        右子树为空，该节点是父亲的右子树，找父节点的父节点的父节点，直到祖先1是其父节点2的左子树，返2节点
 （3）右子树不空，右子树的最左叶子节点，如果没有，就返回右子树。


 */
public class Solution {

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if(pNode == null)
            return null;
        if(pNode.right==null )//右子树为空
        {
            if(pNode.next==null)
                return null;
            else{
                if(pNode == pNode.next.left)//该节点是父亲的左子树
                    return pNode.next;
                else{//该节点是父亲的右子树
                    while(pNode.next!=null && pNode.next.next!=null && pNode.next!=pNode.next.next.left){
                        pNode = pNode.next;
                    }
                    return pNode.next.next;
                }
            }
        }

        else{//右子树不为空
            pNode = pNode.right;
            while(pNode.left!=null){
                pNode = pNode.left;
            }
                return pNode;
        }
    }

    public static void assemble(TreeLinkNode node, TreeLinkNode left, TreeLinkNode right, TreeLinkNode next){
        node.left = left;
        node.right = right;
        node.next = next;
    }
    //                            1
    //                  2                   3
    //             4         5          6          7
    //          8     9   10   11   12   13    14   15
    public static void main(String args[]){

        Solution s = new Solution();
        TreeLinkNode node1 = new TreeLinkNode(1);
        TreeLinkNode node2 = new TreeLinkNode(2);
        TreeLinkNode node3 = new TreeLinkNode(3);
        TreeLinkNode node4 = new TreeLinkNode(4);
        TreeLinkNode node5 = new TreeLinkNode(5);
        TreeLinkNode node6 = new TreeLinkNode(6);
        TreeLinkNode node7 = new TreeLinkNode(7);
        TreeLinkNode node8 = new TreeLinkNode(8);
        TreeLinkNode node9 = new TreeLinkNode(9);
        TreeLinkNode node10 = new TreeLinkNode(10);
        TreeLinkNode node11 = new TreeLinkNode(11);
        TreeLinkNode node12 = new TreeLinkNode(12);
        TreeLinkNode node13 = new TreeLinkNode(13);
        TreeLinkNode node14 = new TreeLinkNode(14);
        TreeLinkNode node15 = new TreeLinkNode(15);

        assemble(node1,node2,node3,null);
        assemble(node2,node4,node5,node2);
        assemble(node3,node6,node7,node3);
        assemble(node4,node8,node9,node2);
        assemble(node5,node10,node11,node2);
        assemble(node6,node12,node13,node3);
        assemble(node7,node14,node15,node3);
        assemble(node8,null,null,node4);
        assemble(node9,null,null,node4);
        assemble(node10,null,null,node5);
        assemble(node11,null,null,node5);
        assemble(node12,null,null,node6);
        assemble(node13,null,null,node6);
        assemble(node14,null,null,node7);
        assemble(node15,null,null,node7);




        System.out.println(s.GetNext(node15).val);
        System.out.print("haha");
    }
}

class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null; //父节点。。。

    TreeLinkNode(int val) {
        this.val = val;
    }
}
